Digital data compression is a technology experiencing accentuated interest in the recent years. In part, this is a consequence of the broad use of personal computers and workstations having high resolution graphic display systems. The volume of the digital data used to represent the video information, as well as the speed with which it must be compressed and decompressed, in the course of storage or transmission has motivated significant investigation in the technologies related to data compression.
A data compression algorithm which has proven to be quite popular was first described in an article entitled "A Universal Algorithm for Sequential Data Compression" by authors Lempel and Ziv, as appeared in the IEEE Transactions on Information Theory, Vol. IT-23, No. 3, pp. 337-343, 1977, generally referred to as the LZ-1 data compression algorithm. The LZ-1 algorithm has been refined in various respects by subsequent investigators, examples being the variance described in U.S. Pat. Nos. 5,003,307 and 5,146,221, the subject matter of which is incorporated by reference herein.
The fundamental concepts which characterize these and other versions of the basic LZ-1 algorithm involve the use of a buffer to store new data and to identify new strings of data which match previously received and processed data. Thereby, new strings of data, typically alphanumeric characters, which match existing strings can be identified by merely referring to an offset and length in an earlier point in the string sequence. The LZ-1 algorithm is dynamic in that new data is entered into the buffer which stores the earlier data after the comparison and encoding of new data is completed. The size of the buffer is analogous to a sliding window over a data stream in which the new data characters are always compared to previously received characters within the length of the window. The encoded output is either a raw/literal character, indicating no compression, or a compressed/string character, providing a length and offset identifying the matching previously existing character string within the window. As would be expected, the algorithm is increasingly effective as the size of the window increases and repetition of the patterns in the data characters within the window increases.
However, the classical LZ-1 algorithm suffers from the need for extensive comparison between the data characters within the window and various combinations of new data characters. As a consequence, implementations involving large sliding window buffers seldom complete exhaustive searches of the window data for data character matches.
The aforementioned U.S. patent application Ser. No. 08/537,569 relates to a high speed hardware implementation of the LZ-1 algorithm, the subject matter which is incorporated by reference herein. U.S. Pat. No. 5,526,472 relates to a toroidally implemented circular bit shift register which is characterized by its high speed of accomplishing linear shift operations in a conventional processor environment. U.S. patent application Ser. No. 08/173,738 relates to a new way of practicing the LZ-1 algorithm, involving the use of a data character addressed history buffer with shifting entries and various registers for comparing, tracking and counting markers associated with the presence and order of data characters.
The data compression implementation according to U.S. patent application Ser. No. 08/173,738 involves extensive shifting of bits in unison within the history table, or individually with selective update, and is therefore not particularly adapted to execution by a conventional processor. Though barrel shifters can be used to shift the markers in the history buffer, the operational widths of barrel shifters typically conform to the processor operand size. In contemporary designs this is 32 bits. In contrast, the length of the bit string of markers in a typical row of the history buffer is at least 512 bits, requiring 16 operations by a 32-bit barrel shifter to complete processing.
Therefore, there remains a need for systems and method which provide exhaustive sliding window data compression while reducing the number of shift operations and minimizing the number of such shift operations to the extent that they do exist.